Leetcode 10.正则表达式匹配

题目描述：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

示例 1：

1
2
3

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3

输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

1
2
3

输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4：

1
2
3

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5：

1
2

输入：s = "mississippi" p = "mis*is*p*."
输出：false

提示：

• $0 <= s.length <= 20$
• $0 <= p.length <= 30$
• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

链接：

https://leetcode-cn.com/problems/regular-expression-matching

题目分析

  对于字符串 s 和 p，我们是逐步匹配的。对于普通字符是一对一匹配，采用一个匹配函数判断即可，对于 . 匹配任意字符的情况也可以在这里得到解决。我们可以采用动态规划的思路，dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。注意 s 和 p 的下标都是从 0 开始的，因此 s 的第 i 个字符是 s[i-1]。那应该有以下的状态转移方程。

• 若 $p[j-1]\neq *$ $$dp[i][j] = \begin{cases} dp[i-1][j-1], & s[i-1] = p[j-1] \\ flase, & s[i-1]\neq p[j-1] \end{cases}$$

  而当出现了字符 * 时，表示我们可以对 p[j-1] 匹配任意次，也包括 0 次。这时候，我们可以分情况，如果是匹配 0 次，则相当于我们直接把 p[j] 和 p[j-1] 去掉。如果是匹配 1 次或多次，我们可以直接认为是匹配 1 次，然后将 s[i] 去掉，而 p[j] 和 p[j-1] 继续保留到下次匹配中。这样的话可以得到下面的状态转移方程。

• 若 $p[j-1]= *$ $$dp[i][j] = \begin{cases} dp[i-1][j]\quad or\quad dp[i][j-2], & s[i-1] = p[j-2] \\ dp[i][j-2], & s[i-1]\neq p[j-2] \end{cases}$$

  我们最后的答案也即 dp[s.size()][p.size()]，也就是两个字符串完全匹配的结果。
  对于边界条件，我们规定 dp[0][0] = true，也即两个空串是匹配的。而由于 p 中可能开头就存在 a* 而匹配到 s 中空串的情况，i 需从 0 开始。另外代码中存在着一定的冗余，例如 p 中的 a* 必须视为一个整体，但是我们在逐步匹配中，首先直接让 a 进行了匹配，这样的匹配是多余的。但是对于这样的情况，在检查到 * 时，我们的状态转移和 dp[x][j-1] 完全没有关系，因此不对最后结果产生任何影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    bool match(char a, char b){
        if(b == '.' || a == b) return true;
        else return false;
    }

    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.size()+1, vector<bool>(p.size()+1));
        dp[0][0] = true;
        for(int i = 0; i <= s.size(); i++){
            for(int j = 1; j <= p.size(); j++){
                if(p[j-1] != '*'){
                    if(i != 0 && match(s[i-1], p[j-1])){
                        dp[i][j] = dp[i-1][j-1];
                    }
                    else dp[i][j] = false;
                }
                else{
                    dp[i][j] = dp[i][j-2];
                    if(i != 0 && match(s[i-1], p[j-2])){
                        dp[i][j] = dp[i-1][j] || dp[i][j];
                    }
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};

  时间复杂度：$O(mn)$，其中 $m、n$ 分别表示字符串 s 和 p 的长度。因为动态规划的状态总数是 $(m+1)*n$，而对于每个状态转移的时间复杂度是 $O(1)$。
  空间复杂度：$O(mn)$，其中 $m、n$ 分别表示字符串 s 和 p 的长度。即存储动态规划状态所需要的空间。